import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LianBao
 * Date: 2024-10-08
 * Time: 14:55
 */
public class Main {
    //移动0
    public void moveZeroes(int[] nums) {
        int dest = -1;
        int cur = 0;
        while (cur < nums.length) {
            if (nums[cur] != 0) {
                //交换
                int tmp = nums[dest + 1];
                nums[dest + 1] = nums[cur];
                nums[cur] = tmp;
                dest++;
            }
            cur++;
        }
    }

    //复写0
    public void duplicateZeros(int[] arr) {
        //1.先找到最后一个复写的0(双指针算法)

        int cur = 0;
        int dest = -1;

        while (cur < arr.length) {
            if (arr[cur] == 0) {
                dest += 2;
            } else {
                dest++;
            }

            if (dest >= arr.length - 1) {
                break;
            }
            cur++;
        }

        //处理边界情况:最后一个复写的数是0,dest的位置可能在arr.length
        if (dest == arr.length) {
            arr[arr.length - 1] = 0;
            dest -= 2;
            cur--;
        }

        //开始复写
        while (cur >= 0) {
            if (arr[cur] != 0) {
                arr[dest] = arr[cur];
                dest--;
            } else {
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
            cur--;
        }
    }

    //快乐数
    public int fun(int num) {
        int sum = 0;
        while (num != 0) {
            sum += (num % 10) * (num % 10);
            num /= 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        //判断n是不是快乐数

        int fast = fun(n);
        int slow = n;
        while (fast != slow) {
            slow = fun(slow);
            fast = fun(fun(fast));
        }

        return fast == 1;
    }

    //盛水最多的容器
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxV = 0;
        while (left < right) {

            int V = (right - left) * Math.min(height[left], height[right]);
            maxV = Math.max(V, maxV);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxV;
    }


    //有效三角形个数: 给定一个包含非负整数的数组nums,返回其中可以组成三角形三条边的三元组个数
    public int triangleNumber(int[] nums) {

        int count = 0;//统计个数
        //先排序
        Arrays.sort(nums);
        int flg = nums.length - 1;//固定最大的数
        while (flg >= 2) {

            //双指针
            int left = 0;
            int right = flg - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[flg]) {
                    //符合三角形
                    count += (right - left);
                } else {
                    left++;
                }
            }
            flg--;
        }
        return count;
    }


    //两数之和(题目说明了已经有序)
    public int[] twoSum(int[] price, int target) {
        int left = 0;
        int right = price.length - 1;

        int[] ret = new int[2];

        while (left < right) {
            int sum = price[left] + price[right];
            if (sum > target) {
                //要小一点
                right--;
            } else if (sum < target) {
                //要大一点
                left++;
            } else {
                ret[0] = price[left];
                ret[1] = price[right];
                break;
            }
        }
        return ret;
    }

    //三数之和
    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);//排序
        int flg = nums.length - 1;//先固定最后一个数

        while (flg >= 2) {
            int target = -nums[flg];
            int left = 0;
            int right = flg - 1;
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {
                    //找到了,添加至结果列表中
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[left]);
                    list.add(nums[right]);
                    list.add(nums[flg]);
                    ret.add(list);
                    //
                    left++;
                    right--;
                    int leftn = nums[left - 1];
                    int rightn = nums[right + 1];

                    //去重操作
                    while (left < right && nums[left] == leftn) {
                        left++;
                    }
                    while (left < right && nums[right] == rightn) {
                        right--;
                    }
                }
            }
            while (flg >= 2 && nums[flg] == (-target)) {
                flg--;
            }
        }
        return ret;
    }

    //4数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {

        List<List<Integer>> ret = new ArrayList<>();

        Arrays.sort(nums);

        int flg1 = nums.length - 1;
        while (flg1 >= 3) {

            int flg2 = flg1 - 1;
            while (flg2 >= 2) {
                int left = 0;
                int right = flg2 - 1;
                while (left < right) {
                    long sum = (long) nums[left] + nums[right] + nums[flg1] + nums[flg2];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[left]);
                        list.add(nums[right]);
                        list.add(nums[flg1]);
                        list.add(nums[flg2]);
                        ret.add(list);
                        left++;
                        right--;
                        int ln = nums[left - 1];
                        int rn = nums[right + 1];
                        //去重
                        while (left < right && nums[left] == ln) {
                            left++;
                        }
                        while (left < right && nums[right] == rn) {
                            right--;
                        }
                    }
                }
                int flg2n = nums[flg2];
                while (flg2 >= 2 && nums[flg2] == flg2n) {
                    flg2--;
                }
            }
            int flg1n = nums[flg1];
            while (flg1 >= 3 && nums[flg1] == flg1n) {
                flg1--;
            }
        }
        return ret;
    }


}
